package com.ismarkendenis.superincreasingknapsack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;

public class SuperIncreasingKnapsack {

	private int w, q, r;
	private int[] oursis = { 1, 4, 6, 13, 26, 54, 111, 233 };
	private int[] examplesis = { 2, 7, 11, 21, 42, 89, 180, 354 };
	private int[] wouterEncryptedMessageArr = { 1142, 258, 761, 874, 874, 1035,
			792, 727, 1066, 1179, 102, 1179, 1357, 905, 761, 102, 727, 436,
			323, 436, 1035, 436, 436, 1244, 102, 436, 1244, 102, 1504, 727,
			1066, 1244, 102, 614, 258, 905, 1148, 761, 436, 1035, 102, 1357,
			583, 102, 1326, 1357, 436, 1244, 1148, 323, 258, 888, 102, 905,
			436, 761, 102, 597, 436, 1035, 727, 710, 614, 761, 436, 1244, 1201,
			1201, 1201, 102, 905, 1357, 436, 761, 102, 727, 1179, 102, 258,
			258, 1244, 102, 614, 436, 761, 102, 1326, 436, 1035, 1179, 215,
			921, 921, 554, 625, 102, 775, 436, 258, 1035, 102, 905, 1165, 102,
			436, 1244, 761, 614, 874, 1148, 727, 258, 1148, 905, 102, 775, 792,
			258, 888, 1148, 102, 1326, 614, 436, 1244, 102, 1035, 436, 258,
			792, 102, 1326, 1357, 1035, 1179, 102, 727, 1148, 102, 323, 436,
			905, 258, 1244, 323, 436, 323, 102, 1357, 775, 102, 905, 436, 1201,
			554, 921, 921, 102, 102, 102, 102, 512, 1201, 481, 1201, 102, 690,
			1357, 1213, 436, 710, 1035, 258, 775, 761, 921 };
	private int ourq = 500;
	private int ourr = 113;
	private int[] bindecoder = { 0, 1, 2, 4, 8, 16, 32, 64, 128, 256};//128, 64, 32, 16, 8, 4, 2, 1, 0 
	private Vector<Integer> wouterEncryptedMessageVector = new Vector<Integer>();

	public SuperIncreasingKnapsack() {
		Vector<Integer> sis = getSuperIncreasingSequenceVector(oursis);
		w = sum(sis);
		q = ourq;
		r = ourr;
		Vector<Integer> pk = getPublicKey(sis, r, q);
		Vector<Integer> encryptedMessage = encrypt("p", pk);
		System.out.println(decrypt(arrToVector(wouterEncryptedMessageArr), r, q, sis));
	}

	private int sum(Vector<Integer> superincreasingsequence) {
		int sum = 0;
		Iterator<Integer> it = superincreasingsequence.iterator();
		while (it.hasNext()) {
			sum += it.next();
		}
		return sum;
	}

	private Vector<Integer> getSuperIncreasingSequenceVector(int[] sis) {
		Vector<Integer> superincreasingsequence = new Vector<Integer>(8);
		superincreasingsequence.add(new Integer(sis[0]));
		superincreasingsequence.add(new Integer(sis[1]));
		superincreasingsequence.add(new Integer(sis[2]));
		superincreasingsequence.add(new Integer(sis[3]));
		superincreasingsequence.add(new Integer(sis[4]));
		superincreasingsequence.add(new Integer(sis[5]));
		superincreasingsequence.add(new Integer(sis[6]));
		superincreasingsequence.add(new Integer(sis[7]));
		return superincreasingsequence;
	}

	private Vector<Integer> getPublicKey(
			Vector<Integer> superincreasingsequence, int r, int q) {
		Vector<Integer> publickey = new Vector<Integer>(8);
		Iterator<Integer> it = superincreasingsequence.iterator();
		while (it.hasNext()) {
			int key = (it.next() * r) % q;
			publickey.add(key);
		}
		return publickey;
	}
	
	/**
	 * 
	 * @param message
	 * @param publicKey
	 * @return
	 */
	private Vector<Integer> encrypt(String message, Vector<Integer> publicKey) {
		
		Vector<Integer> encryptedMessage = new Vector<Integer>(message.length());
		
		char[] characters = message.toCharArray();
		
		for (int i = 0; i < characters.length; i++) {
			
			char[] bits = new StringBuffer(Integer.toBinaryString((int) (characters[i]))).reverse().toString()
					.toCharArray();
			int encryptedChar = 0;
			
			for (int j = 0; j < bits.length; j++) {
				if (bits[j] == 49) {
					encryptedChar += publicKey.get(j + 1);
				}
			}
			
			encryptedMessage.add(encryptedChar);
		}
		
		return encryptedMessage;
	}

	/**
	 * 
	 * @param encryptedMessage
	 * @param r
	 * @param q
	 * @param sis
	 * @return
	 */
	private String decrypt(Vector<Integer> encryptedMessage, int r, int q,
			Vector<Integer> sis) {
		String decryptedMessage = "";
		Iterator<Integer> it = encryptedMessage.iterator();
		
		while (it.hasNext()) {
			int invr = (it.next() * modInverse(r, q)) % q;
			int[] code = { 0, 0, 0, 0, 0, 0, 0, 0 };
			
			while (invr != 0) {
				Iterator<Integer> it2 = sis.iterator();

				boolean found = false;
				int previous = 0;
				int current = 0;
				int index = 0;

				while (it2.hasNext() && !found) {

					current = it2.next();
					if (current > invr) {
						invr -= previous;
						found = true;
						code[index] = 1;
					}
					index++;
					previous = current;
				}
				if (!found) {
					invr -= previous;
					code[7] = 1;
				}
			}
			int decrypted = 0;
			for (int i = 1; i < code.length; i++) {
				if (code[i] == 1) {
					decrypted += bindecoder[i];
				}
			}
			decryptedMessage += ((char) decrypted);
		}
		return decryptedMessage;
	}

	private int modInverse(int a, int n) {
		int i = n, v = 0, d = 1;
		while (a > 0) {
			int t = i / a, x = a;
			a = i % x;
			i = x;
			x = d;
			d = v - t * x;
			v = x;
		}
		v %= n;
		if (v < 0)
			v = (v + n) % n;
		return v;
	}
	
	private Vector<Integer> arrToVector(int[] arr){
		Vector<Integer> returnVector = new Vector<Integer>();
		for(int i: arr){
			returnVector.add(i);
		}
		return returnVector;
	}

}
